package lcof;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.*;
import java.util.stream.Collectors;

public class FindSubstring30 {

    public List<Integer> findSubstring(String s, String[] words) {
        //初始化返回值
        List<Integer> res = new ArrayList<>();
        //单词长度
        int wordLen = words[0].length();
        //子串的长度
        int subLen = wordLen * words.length;
        if (subLen > s.length()) {
            return res;
        }
        // 使用Stream API进行处理并应用自定义合并函数
        Map<String, Integer> map = Arrays.stream(words)
                .collect(Collectors.toMap(
                        str -> str,  // keyMapper: 将字符串映射为其自身作为键
                        str -> 1,    // valueMapper: 每个字符串的初始计数值为1
                        Integer::sum)); // 自定义的合并函数
        //以words[0].length 进行循环起点；多次滑动
        for (int start = 0; start < wordLen; start++) {
            //后续长度不够子串要求
            if (subLen > s.length() - start) {
                break;
            }
            Map<String, Integer> copy = new HashMap<>(map);
            //步长为wordLen
            for (int l = start, r = start; r <= s.length() - wordLen; r = r + wordLen) {
                String current = s.substring(r, r + wordLen);
                //判断是否属于给定范围
                if (!map.containsKey(current)) {
                    //恢复左边消耗过的次数
                    while (l < r) {
                        String add = s.substring(l, l + wordLen);
                        copy.put(add, copy.get(add) + 1);
                        l += wordLen;
                    }
                    //不属于给定范围，从current往后
                    l = r + wordLen;
                    continue;
                }
                //属于给定范围,减少一个次数
                Integer curNumb = copy.get(current);
                if (curNumb == 0) {
                    //无多余可用。需要移动左区间
                    while (l < r) {
                        String add = s.substring(l, l + wordLen);
                        l += wordLen;
                        if (add.equals(current)) {
                            break;
                        }
                        copy.put(add, copy.get(add) + 1);
                    }
                } else {
                    //有多余可用。直接扣减
                    copy.put(current, curNumb - 1);
                }
                //记录condition
                if (isCorrect(copy)) {
                    res.add(l);
                }
            }
        }
        return res;

    }

    private boolean isCorrect(Map<String, Integer> copy) {
        boolean b = copy.entrySet().stream().anyMatch(o -> o.getValue() > 0);
        return !b;
    }


    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] arr =  new int[128];
        Set<Character> set = new HashSet<>();

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            set.add(c);
            arr[c]++;
        }

        for (int i = 0; i < t.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                arr[c]--;
            }
        }
        if (valid(arr)) {
            return s.substring(0, t.length());
        }
        int indexL = 0;
        int indexR = s.length();
        boolean res = false;
        for (int l=0,r=t.length(); r < s.length(); r++) {
            //右增加字符计数
            char c = s.charAt(r);
            if (set.contains(c)) {
                arr[c]--;
            }
            //当条件成立，可以左移子串，尝试缩小窗口
            while (valid(arr)) {
                if (r - l < indexR - indexL) {
                    indexL = l;
                    indexR = r+1;
                    res = true;
                }
                if (set.contains(s.charAt(l))) {
                    arr[s.charAt(l)]++;
                }
                l++;
            }
        }
        if (res) {
            return s.substring(indexL, indexR);
        }
        return "";
    }

    private boolean valid(int[] arr) {
        for (int i : arr) {
            if (i > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 仅保留一个变量作为valid校验=
     */
    public static String minWindow2(String s, String t) {
        //s字符次数减去s字符次数
        int[] arr = new int[128];
        //去重后的字符
        int distinct = 0;
        //累计s出现的次数
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (arr[c] == 0) {
                distinct++;
            }
            arr[c]++;
        }
        //滑动窗口
        int indexL = -1, indexR = s.length();
        for (int l = 0, r = 0; r < s.length(); r++) {
            //将r端点放入,扣除数量
            char c = s.charAt(r);
            arr[c]--;
            if (arr[c] == 0) {
                distinct--;
            }
            //满足区间条件
            while (distinct == 0) {
                //记录最短长度
                if (r - l < indexR - indexL) {
                    indexL = l;
                    indexR = r;
                }
                //此时l字符刚好足够，现在l移动后，就不够了
                if (arr[s.charAt(l)] == 0) {
                    distinct++;
                }
                arr[s.charAt(l)]++;
                l++;
            }
        }
        return indexL == -1 ? "" : s.substring(indexL, indexR + 1);
    }

    public static void main(String[] args) {
        minWindow2("aa", "aa");
    }

}
